The number of applications that take advantage of services offered by computer networks is large and growing. Such applications include interactive multimedia communication, multimedia file retrieval, streaming media distribution, and distributed computing. A basic service typically provided by a modern computer network is the ability for each computer in the network to establish a communication connection with any other computer in the network. Particularly in large computer networks, it is common for this service to be provided by sophisticated routing rather than, for example, brute each-to-each (N×N) connectivity. For at least the purposes of this description, the computer network involved in providing this basic service is called the transport network.
Various application architectures may utilize the transport network in different ways. For example, a client-server architecture may have a centralized server component and a number of client components, located throughout the transport network, that establish more or less temporary communication connections with the server as required. Another example is the recently popular peer-to-peer (P2P) architecture. Peer-to-peer architectures typically avoid centralized elements, instead relying on peers with roughly equivalent functionality to provide the backbone of the application. The benefits of such decentralization may include avoiding single points of failure and vulnerability to attack, as well as good theoretical scalability.
There are various conventional schemes for arranging peers in a peer-to-peer architecture. Examples of such schemes include the CAN architecture described by Ratnasamy et al. in A Scalable Content-Addressable Network, Proceedings of ACM SIGCOMM, August 2001, the Chord architecture described by Stoica et al. in Chord: A scalable Peer-to-peer Lookup Service for Internet Applications, Proceedings of ACM SIGCOMM, August 2001, the Pastry architecture described by Rowstron et al. in Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems, Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001), November 2001, and the Tapestry architecture described by Zhao et al. in Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing, Report No. UCB/CSD-01-1141, Computer Science Division, University of California, Berkeley, April 2001. In general, peers in a peer-to-peer architecture are arranged in a network, called an overlay network, which may be considered independently of the underlying transport network.
A problem with constructing the overlay network of a peer-to-peer architecture independently of the transport network is that peers that are neighbors in the overlay network may be far from each other in the underlying transport network and so, for example, may experience long delays when communicating with each other. This discord between the overlay network and the transport network is not wholly undesirable because, for example, it may enable the overlay network, and thus an application utilizing it, to tolerate failures in the transport network. However, many applications that desire the advantages of overlay networks, particularly those with high quality of service (QoS) requirements, would benefit from a system and method for constructing overlay networks that make efficient use of the underlying transport network.